package leetcode.code1462;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Solution2 {
	public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
		List<Integer>[] nexts = new ArrayList[numCourses];
		for (int i = 0; i < nexts.length; i++) {
			nexts[i] = new ArrayList<>();
		}
		for (int i = 0; i < prerequisites.length; i++) {
			nexts[prerequisites[i][0]].add(prerequisites[i][1]);
		}
		boolean[][] pres = new boolean[numCourses][numCourses];
		boolean[] from = new boolean[numCourses];
		for (int i = 0; i < numCourses; i++) {
			if (!from[i]) {
				from[i] = true;
				this.f(i, pres, new HashSet<>(), nexts, from);
			}
		}
		List<Boolean> ans = new ArrayList<>();
		for (int i = 0; i < queries.length; i++) {
			ans.add(pres[queries[i][0]][queries[i][1]]);
		}
		return ans;
	}

	private void f(int course, boolean[][] pres, Set<Integer> preSet, List<Integer>[] nexts, boolean[] from) {
		for (int pre : preSet) {
			pres[pre][course] = true;
		}
		preSet.add(course);
		for (int next : nexts[course]) {
			if (!from[next]) {
				from[next] = true;
				this.f(next, pres, new HashSet<>(preSet), nexts, from);
			}
		}
	}
}
